package io.github.hadyang.leetcode.offer;

import io.github.hadyang.leetcode.TreeNode;

/** @author haoyang.shi */
public class BSTLinkConvert {

  public TreeNode Convert(TreeNode pRootOfTree) {
    if (pRootOfTree == null) {
      return null;
    }

    TreeNode[] nodeList = {new TreeNode(-1)};

    ConvertToLink(pRootOfTree, nodeList);

    TreeNode cursor = pRootOfTree;
    while (cursor.left != null) {
      cursor = cursor.left;
    }

    cursor.right.left = null;
    return cursor.right;
  }

  private void ConvertToLink(TreeNode root, TreeNode[] nodeList) {
    if (root == null) {
      return;
    }

    ConvertToLink(root.left, nodeList);

    root.left = nodeList[0];
    nodeList[0].right = root;
    nodeList[0] = root;

    ConvertToLink(root.right, nodeList);
  }
}
